Digital video consumes large amounts of storage and transmission capacity. A typical raw digital video sequence includes 15 or 30 pictures per second. Each picture can include tens or hundreds of thousands of pixels (also called pels). Each pixel represents a tiny element of the picture. In raw form, a computer commonly represents a pixel with 24 bits or more. Thus, the number of bits per second, or bit rate, of a typical raw digital video sequence can be 5 million bits/second or more.
Most computers and computer networks lack the resources to process raw digital video. For this reason, engineers use compression (also called coding or encoding) to reduce the bit rate of digital video. Compression can be lossless, in which quality of the video does not suffer but decreases in bit rate are limited by the complexity of the video. Or, compression can be lossy, in which quality of the video suffers but decreases in bit rate are more dramatic. Decompression reverses compression.
In general, video compression techniques include “intra” compression and “inter” or predictive compression. Intra compression techniques compress individual pictures, typically called I-frames or key frames. Inter compression techniques compress frames with reference to preceding and/or following frames, and inter-compressed frames are typically called predicted frames, P-frames, or B-frames.
I. Inter Compression in Windows Media Video, Versions 8 and 9
Microsoft Corporation's Windows Media Video, Version 8 [“WMV8”] includes a video encoder and a video decoder. The WMV8 encoder uses intra and inter compression, and the WMV8 decoder uses intra and inter decompression. Windows Media Video, Version 9 [“WMV9”] uses a similar architecture for many operations.
Inter compression in the WMV8 encoder uses block-based motion compensated prediction coding followed by transform coding of the residual error. FIGS. 1 and 2 illustrate the block-based inter compression for a predicted frame in the WMV8 encoder. In particular, FIG. 1 illustrates motion estimation for a predicted frame 110 and FIG. 2 illustrates compression of a prediction residual for a motion-compensated block of a predicted frame.
For example, in FIG. 1, the WMV8 encoder computes a motion vector for a macroblock 115 in the predicted frame 110. To compute the motion vector, the encoder searches in a search area 135 of a reference frame 130. Within the search area 135, the encoder compares the macroblock 115 from the predicted frame 110 to various candidate macroblocks in order to find a candidate macroblock that is a good match. The encoder outputs information specifying the motion vector (entropy coded) for the matching macroblock.
Since a motion vector value is often correlated with the values of spatially surrounding motion vectors, compression of the data used to transmit the motion vector information can be achieved by selecting a motion vector predictor based upon motion vectors of neighboring macroblocks and predicting the motion vector for the current macroblock using the motion vector predictor. The encoder can encode the differential between the motion vector and the predictor. After reconstructing the motion vector by adding the differential to the predictor, a decoder uses the motion vector to compute a prediction macroblock for the macroblock 115 using information from the reference frame 130, which is a previously reconstructed frame available at the encoder and the decoder. The prediction is rarely perfect, so the encoder usually encodes blocks of pixel differences (also called the error or residual blocks) between the prediction macroblock and the macroblock 115 itself.
FIG. 2 illustrates an example of computation and encoding of an error block 235 in the WMV8 encoder. The error block 235 is the difference between the predicted block 215 and the original current block 225. The encoder applies a discrete cosine transform [“DCT”] 240 to the error block 235, resulting in an 8×8 block 245 of coefficients. The encoder then quantizes 250 the DCT coefficients, resulting in an 8×8 block of quantized DCT coefficients 255. The encoder scans 260 the 8×8 block 255 into a one-dimensional array 265 such that coefficients are generally ordered from lowest frequency to highest frequency. The encoder entropy encodes the scanned coefficients using a variation of run length coding 270. The encoder selects an entropy code from one or more run/level/last tables 275 and outputs the entropy code.
FIG. 3 shows an example of a corresponding decoding process 300 for an inter-coded block. In summary of FIG. 3, a decoder decodes (310, 320) entropy-coded information representing a prediction residual using variable length decoding 310 with one or more run/level/last tables 315 and run length decoding 320. The decoder inverse scans 330 a one-dimensional array 325 storing the entropy-decoded information into a two-dimensional block 335. The decoder inverse quantizes and inverse discrete cosine transforms (together, 340) the data, resulting in a reconstructed error block 345. In a separate motion compensation path, the decoder computes a predicted block 365 using motion vector information 355 for displacement from a reference frame. The decoder combines 370 the predicted block 365 with the reconstructed error block 345 to form the reconstructed block 375.
The amount of change between the original and reconstructed frames is the distortion and the number of bits required to code the frame indicates the rate for the frame. The amount of distortion is roughly inversely proportional to the rate.
II. Interlaced Video and Progressive Video
A video frame contains lines of spatial information of a video signal. For progressive video, these lines contain samples starting from one time instant and continuing through successive lines to the bottom of the frame. A progressive I-frame is an intra-coded progressive video frame. A progressive P-frame is a progressive video frame coded using forward prediction, and a progressive B-frame is a progressive video frame coded using bi-directional prediction.
A typical interlaced video frame consists of two fields scanned starting at different times. For example, referring to FIG. 4, an interlaced video frame 400 includes top field 410 and bottom field 420. Typically, the even-numbered lines (top field) are scanned starting at one time (e.g., time t) and the odd-numbered lines (bottom field) are scanned starting at a different (typically later) time (e.g., time t+1). This timing can create jagged tooth-like features in regions of an interlaced video frame where motion is present because the two fields are scanned starting at different times. For this reason, interlaced video frames can be rearranged according to a field structure, with the odd lines grouped together in one field, and the even lines grouped together in another field. This arrangement, known as field coding, is useful in high-motion pictures for reduction of such jagged edge artifacts. On the other hand, in stationary regions, image detail in the interlaced video frame may be more efficiently preserved without such a rearrangement. Accordingly, frame coding is often used in stationary or low-motion interlaced video frames, in which the original alternating field line arrangement is preserved.
A typical progressive video frame consists of one frame of content with non-alternating lines. In contrast to interlaced video, progressive video does not divide video frames into separate fields, and an entire frame is scanned left to right, top to bottom starting at a single time.
III. P-Frame Coding and Decoding in a Previous WMV Encoder and Decoder
A previous WMV encoder and decoder use progressive and interlace coding and decoding in P-frames. In interlaced and progressive P-frames, a motion vector is encoded in the encoder by computing a differential between the motion vector and a motion vector predictor, which is computed based on neighboring motion vectors. And, in the decoder, the motion vector is reconstructed by adding the motion vector differential to the motion vector predictor, which is again computed (this time in the decoder) based on neighboring motion vectors. Thus, a motion vector predictor for the current macroblock or field of the current macroblock is selected based on the candidate motion vector predictors, and a motion vector differential is calculated based on the predictor. The motion vector can be reconstructed by adding the motion vector differential to the selected motion vector predictor at either the encoder or the decoder side. Typically, luminance motion vectors are reconstructed from the encoded motion information, and chrominance motion vectors are derived from the reconstructed luminance motion vectors.
A. Progressive P-Frame Coding and Decoding
For example, in the encoder and decoder, progressive P-frames can contain macroblocks encoded in one motion vector (1MV) mode or in four motion vector (4MV) mode, or skipped macroblocks, with a decision generally made on a macroblock-by-macroblock basis. P-frames with only 1MV macroblocks (and, potentially, skipped macroblocks) are referred to as 1MV P-frames, and P-frames with both 1MV and 4MV macroblocks (and, potentially, skipped macroblocks) are referred to as Mixed-MV P-frames. One luma motion vector is associated with each 1MV macroblock, and up to four luma motion vectors are associated with each 4MV macroblock (one for each block).
FIGS. 5A and 5B are diagrams showing the locations of macroblocks considered for candidate motion vector predictors for a macroblock in a 1MV progressive P-frame. The candidate predictors are taken from the left, top and top-right macroblocks, except in the case where the macroblock is the last macroblock in the row. In this case, Predictor B is taken from the top-left macroblock instead of the top-right. For the special case where the frame is one macroblock wide, the predictor is always Predictor A (the top predictor). When Predictor A is out of bounds because the macroblock is in the top row, the predictor is Predictor C. Various other rules address other special cases such as intra-coded predictors.
FIGS. 6A-10 show the locations of the blocks or macroblocks considered for the up-to-three candidate motion vectors for a motion vector for a 1MV or 4MV macroblock in a Mixed-MV frame. In the following figures, the larger squares are macroblock boundaries and the smaller squares are block boundaries. For the special case where the frame is one macroblock wide, the predictor is always Predictor A (the top predictor). Various other rules address other special cases such as top row blocks for top row 4MV macroblocks, top row 1MV macroblocks, and intra-coded predictors.
FIGS. 6A and 6B are diagrams showing locations of blocks considered for candidate motion vector predictors for a 1MV current macroblock in a Mixed-MV frame. The neighboring macroblocks may be 1MV or 4MV macroblocks. FIGS. 6A and 6B show the locations for the candidate motion vectors assuming the neighbors are 4MV (i.e., predictor A is the motion vector for block 2 in the macroblock above the current macroblock, and predictor C is the motion vector for block 1 in the macroblock immediately to the left of the current macroblock). If any of the neighbors is a 1MV macroblock, then the motion vector predictor shown in FIGS. 5A and 5B is taken to be the motion vector predictor for the entire macroblock. As FIG. 6B shows, if the macroblock is the last macroblock in the row, then Predictor B is from block 3 of the top-left macroblock instead of from block 2 in the top-right macroblock as is the case otherwise.
FIGS. 7A-10 show the locations of blocks considered for candidate motion vector predictors for each of the 4 luminance blocks in a 4MV macroblock. FIGS. 7A and 7B are diagrams showing the locations of blocks considered for candidate motion vector predictors for a block at position 0; FIGS. 8A and 8B are diagrams showing the locations of blocks considered for candidate motion vector predictors for a block at position 1; FIG. 9 is a diagram showing the locations of blocks considered for candidate motion vector predictors for a block at position 2; and FIG. 10 is a diagram showing the locations of blocks considered for candidate motion vector predictors for a block at position 3. Again, if a neighbor is a 1MV macroblock, the motion vector predictor for the macroblock is used for the blocks of the macroblock.
For the case where the macroblock is the first macroblock in the row, Predictor B for block 0 is handled differently than block 0 for the remaining macroblocks in the row (see FIGS. 7A and 7B). In this case, Predictor B is taken from block 3 in the macroblock immediately above the current macroblock instead of from block 3 in the macroblock above and to the left of current macroblock, as is the case otherwise. Similarly, for the case where the macroblock is the last macroblock in the row, Predictor B for block 1 is handled differently (FIGS. 8A and 8B). In this case, the predictor is taken from block 2 in the macroblock immediately above the current macroblock instead of from block 2 in the macroblock above and to the right of the current macroblock, as is the case otherwise. In general, if the macroblock is in the first macroblock column, then Predictor C for blocks 0 and 2 are set equal to 0.
B. Interlaced P-Frame Coding and Decoding in the Encoder and Decoder
The encoder and decoder use a 4:1:1 macroblock format for interlaced P-frames, which can contain macroblocks encoded in field mode or in frame mode, or skipped macroblocks, with a decision generally made on a macroblock-by-macroblock basis. Two motion vectors are associated with each field-coded inter-macroblock (one motion vector per field), and one motion vector is associated with each frame-coded inter-macroblock. An encoder jointly encodes motion information, including horizontal and vertical motion vector differential components, potentially along with other signaling information.
FIGS. 11, 12 and 13 show examples of candidate predictors for motion vector prediction for frame-coded 4:1:1 macroblocks and field-coded 4:1:1 macroblocks, respectively, in interlaced P-frames in the WMV encoder and decoder. FIG. 11 shows candidate predictors A, B and C for a current frame-coded 4:1:1 macroblock in an interior position in an interlaced P-frame (not the first or last macroblock in a macroblock row, not in the top row). Predictors can be obtained from different candidate directions other than those labeled A, B, and C (e.g., in special cases such as when the current macroblock is the first macroblock or last macroblock in a row, or in the top row, since certain predictors are unavailable for such cases). For a current frame-coded macroblock, predictor candidates are calculated differently depending on whether the neighboring macroblocks are field-coded or frame-coded. For a neighboring frame-coded macroblock, the motion vector is simply taken as the predictor candidate. For a neighboring field-coded macroblock, the candidate motion vector is determined by averaging the top and bottom field motion vectors.
FIGS. 12 and 13 show candidate predictors A, B and C for a current field in a field-coded 4:1:1 macroblock in an interior position in the field. In FIG. 12, the current field is a bottom field, and the bottom field motion vectors in the neighboring macroblocks are used as candidate predictors. In FIG. 13, the current field is a top field, and the top field motion vectors in the neighboring macroblocks are used as candidate predictors. Thus, for each field in a current field-coded macroblock, the number of motion vector predictor candidates for each field is at most three, with each candidate coming from the same field type (e.g., top or bottom) as the current field. Again, various special cases (not shown) apply when the current macroblock is the first macroblock or last macroblock in a row, or in the top row, since certain predictors are unavailable for such cases.
To select a predictor from a set of predictor candidates, the encoder and decoder use different selection algorithms, such as a median-of-three algorithm. A procedure for median-of-three prediction is described in pseudo-code 1400 in FIG. 14.
IV. Standards for Video Compression and Decompression
Several international standards relate to video compression and decompression. These standards include the Motion Picture Experts Group [“MPEG”] 1, 2, and 4 standards and the H.261, H.262 (another title for MPEG 2), H.263 and H.264 (also called JVT/AVC) standards from the International Telecommunication Union [“ITU”]. These standards specify aspects of video decoders and formats for compressed video information. Directly or by implication, they also specify certain encoder details, but other encoder details are not specified. These standards use (or support the use of) different combinations of intraframe and interframe decompression and compression.
A. Motion Estimation/Compensation in the Standards
One of the primary methods used to achieve data compression of digital video sequences in the international standards is to reduce the temporal redundancy between pictures. These popular compression schemes (MPEG-1, MPEG-2, MPEG-4, H.261, H.263, etc.) use motion estimation and compensation. For example, a current frame is divided into uniform square regions (e.g., blocks and/or macroblocks). A matching region for each current region is specified by sending motion vector information for the region. The motion vector indicates the location of the region in a previously coded (and reconstructed) reference frame that is to be used as a predictor for the current region. A pixel-by-pixel difference, called the error signal, between the current region and the region in the reference frame is derived. This error signal usually has lower entropy than the original signal. Therefore, the information can be encoded at a lower rate. As in WMV 8 and 9 encoders and decoders, since a motion vector value is often correlated with spatially surrounding motion vectors, compression of the data used to represent the motion vector information can be achieved by coding the differential between the current motion vector and a motion vector predictor that is based upon previously coded, neighboring motion vectors.
Some international standards describe motion estimation and compensation in interlaced video frames. For example, Section 7.6.1 of the MPEG-2 standard describes a dual-prime encoding mode. In dual-prime encoding only one motion vector is encoded (in its full format) in the bitstream together with a differential motion vector. In the case of field pictures, two motion vectors are derived from this information. The two derived motion vectors are used to form predictions from two reference fields (one top field and one bottom field) which are averaged to form the final prediction. In the case of frame pictures, this process is repeated for the two fields so that a total of four field predictions are made.
The May 28, 1998 committee draft of the MPEG4 standard describes motion compensation for interlaced and progressive video. Section 7.5.5 describes motion compensation in progressive video object planes (VOPs). Candidate motion vectors are collected from neighboring macroblocks or blocks. Candidate motion vectors from outside the VOP are treated as not valid. If only one candidate motion vector is not valid, it is set to 0. If only two are not valid, they are set to equal the third motion vector. If all three are not valid, they are set to 0. Median filtering is performed on the three candidates to calculate a predictor.
Section 7.6.2 of the committee draft of the MPEG-4 standard describes motion compensation for interlaced video. For example, Section 7.6.2.1 describes field-predicted macroblocks with one motion vector for each field, and frame-predicted macroblocks with either one motion vector per block or one motion vector per macroblock. Candidate motion vectors are collected from neighboring macroblocks or blocks, with the predictor selected by median filtering.
Section 8.4 of draft JVT-D157 of the JVT/AVC standard also describes motion compensation. The components of a motion vector of a current block are predicted using median prediction. (Prediction does not take place across boundaries of macroblocks that do not belong to the same slice.) First, the motion vector values and reference pictures of three candidate neighboring blocks are determined. If the top right block is outside the current picture or slice or not available due to decoding order, the motion vector and reference picture of the top right block are considered equal to those of the top left block. If the top, top right, and top left blocks are all outside the current picture or slice, their motion vectors and reference pictures are considered equal to those of the left block. In other cases, the motion vector value for a candidate predictor block that is intra-coded or outside the current picture or slice is considered to be 0, and the reference picture is considered to be different than the current block.
Once the motion vector values and reference pictures of the candidate predictors have been determined, if only one of the left, top, and top right blocks has the same reference picture as the current block, the predicted motion vector for the current block is equal to the motion vector value of the block with the same reference picture. Otherwise, each component of the predicted motion vector value for the current block is calculated as the median of the corresponding candidate motion vector component values of the left, top and top right blocks.
Section 8.4 also describes macroblock-adaptive frame/field coding. In interlaced frames, macroblocks are grouped into macroblock pairs (top and bottom). Macroblock pairs can be field-coded or frame-coded. In a frame-coded macroblock pair, the macroblock pair is decoded as two frame-coded macroblocks. In a field-coded macroblock pair, the top macroblock consists of the top-field lines in the macroblock pair, and the bottom macroblock consists of the bottom-field lines in the macroblock pair. If the current block is in frame coding mode, the candidate motion vectors of the neighboring blocks are also frame-based. If the current block is in field-coding mode, the candidate motion vectors of the neighboring blocks are also field-based, in the same field parity.
B. Limitations of the Standards
These international standards are limited in several important ways. For example, draft JVT-d 157 of the JVT/AVC standard and the committee draft of the MPEG-4 standard describe using median prediction to calculate motion vector predictors even when one or more candidate motion vectors are set to 0. Using median prediction when candidates are set to 0 often produces skewed motion vector predictors. The standards also do not describe predicting macroblocks with four coded field motion vectors, which places restrictive limitations on the spatial adaptivity of motion estimation and compensation. Furthermore, draft JVT-d157 performs interlaced coding and decoding through the use of macroblock pairs rather than through individual interlaced macroblocks, which limits the adaptivity of field-coding/frame-coding within a picture.
Given the critical importance of video compression and decompression to digital video, it is not surprising that video compression and decompression are richly developed fields. Whatever the benefits of previous video compression and decompression techniques, however, they do not have the advantages of the following techniques and tools.